CEDEC2015 Day2 メモとか

概要

メモ

GPGPUを活用した剛体シミュレーション最適化事例

GPUが得意なこと

特殊効果的なやつ

物量で賑やかな画面を演出する

精度はそこそこなんだけど大量。

拘束ソルバーって何

衝突検出、反発力計算、移動

Collision Detection, Constraint Solver, Integration

これのConstraint Solverのところ。

A,B,Cの三つの物体がぶつかる時、A-B,B-C,C-A間で、全ての物体同士が貫通しない、というような三つの拘束に対しての解が欲しい

→ヤコビ法、ガウズザイデル法とかで解ける。ただし不等式がふくまれるので、一意にならない。ので、反復解法というのを使う

解決条件を満たしている解λを0~無限の範囲でクランプ(保持？)

0に近い値を望む。

拘束式

CEDEC 2008 物理エンジンの作り方

というのがあるのでみよう。

ヤコビアン:変換マトリクス。速度を拘束軸上に変換する。

拘束軸上？:衝突ポイント上に存在するベクトルみたいなものぽい

式の名前かな

ガウスザイデル法を高速に解く

A-B

B-C

A - C

C-D

同じ剛体を共有しないものは個別に計算できる。

で。

ヤコビ法について、

並列にできる部分を上記のようにみなす方法をつかってみたところ、あんまりよくなかった。

・並列性の悪化

・並列化のためのコストがあった。。

なんで？

計算内容とその反映タイミングの問題。

・ガウズザイデル法だと結果が収束する

・ヤコビ法だと結果が発散する

なので、

・ペア同士の計算はザイデル

・ペア全体の計算はヤコビ

と振ることで、計算量の削減をはかりつつ、、みたいな話

ヤコビ法について

SOR

SUR

SURを適応するとデルタが小さくなって解が発散しにくくなる(解が定まりやすくなる

Weightみたいなパラメータを追加してSURとして適応する

出し方いろいろ。とりあえずインデクシングしまくるみたいなかんじ。

Biasの追加

めりこんだぶんを速度に加える。

貫通してる方向と深さに対して反発力を追加する、みたいな話

反復回数少なくてもいいかんじに動く、みたいなのが目標。

結論

・ガウスザイデル法より修正を加えたヤコビ速くて軽い

・物量が増えてくるとだんだん同じような結果を出す感じになる

・ただ量が増えてくるとメモリアクセスやらで減速する

メモリアクセス周り

流体、粒子ベースシミュレーションで得られた知見

メモリアクセスの効率化

データ構造の変換による効率改善

Array of struct

Struct of array

AOS:

{

pos

vel

}

SOR:

{

pos[N]

vel[N]

}

SOAのほうがキャッシュヒット率良いよ(無駄なデータを読まないので

空間充填曲線をつかってメモリアクセス局在性の最適化

「もし座標上近い物体が隣接したメモリポイントに存在すれば、キャッシュヒット改善するんじゃね？」

テクスチャのピクセル配置に対して、

swizzle化という処理を行うことで、テクスチャ座標上で近いテクスチャのポインタがそれぞれ隣接するといいなみたいな。

空間充填曲線

Z曲線

ヒルベルト曲線とか

「スクリーン座標上でも近いピクセルは、テクスチャ上でも近い、みたいな法則を利用する。」

モートンコード

・低コストで扱える空間充填曲線

メモリをソートした結果、3~4倍の高速化

ソートにかかる処理の重さに比べて圧倒的に高速化のメリットが出る

なるほどな～～

モートンコードのコードはなんかサンプル見よう。

hash gridとも相性がいい

ありあまる演算資源をどのように使い切るか

そうだAsyncShader使おうみたいな話

サブディビジョンサーフェスのすべてがわかる・グラフィックスエンジニア向け理論編

資料発表が発表終了直後だったのでありがたくよみかえしている。

http://takahito-tejima.github.io